package cn.hy.hot100;

import java.util.Stack;

class Solution_42 {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int idx = stack.pop();
                // 弹出相同高度 的位置
                while (!stack.isEmpty() && height[stack.peek()] == height[idx]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    int left = stack.peek();
                    // 能贡献的水量 =  （低柱子- 底座）  *  长度（3-1-1）
                    ans += (Math.min(height[left], height[i]) - height[idx]) * (i - left - 1);
                }
            }
            stack.push(i);
        }
        return ans;
    }
}